#include <stdio.h>
#include <stdlib.h>
#include "h/binsearchtree.h"

typedef BinSeaTree Tree;
typedef Bstnode Node;
typedef BstCompCall Comp;

typedef struct pair {
    Node * parent;
    Node * child;
} Pair;

static void copyItemToNode(Item, Node *);

static Node * makeNode(const Item * item);
static void addNode(Node *, Node *, Comp);
static Pair seekItem(const Item * pi, const Tree * pt, Comp comp);
static void delNode(Node **);
static void inOrder(const Node *, BstCall);

static void dfClear(void * bstn);
//static void dfRmItem(const Item *, Node *, Node *);
//static void rmItemLink(Node *, Node *);
//static bool dfs_flag;
//static Comp comp;
//static Node * newRoot;      //当删除根节点时,这里记录新的根节点

void InitializeBstree(Tree * pbst)
{
    pbst->root = NULL;
    pbst->len = 0;
}

bool BstreeIsEmpty(const Tree * pbst)
{
    return pbst->len == 0;
}

bool BstreeIsFull(const Tree * pbst)
{
    return pbst->len == MAX_BIN_SEA_TREE;
}

int BstreeCountItem(const Tree * pbst)
{
    return pbst->len;
}

bool BstreeAddItem(Item * item, Tree * pbst, Comp call)
{
    Node * newn;
    Pair pa;

    if ((pa = seekItem(item, pbst, call)).child != NULL) {
        ++pa.child->count;
        return true;
    }

    if (BstreeIsFull(pbst))
        return false;

    newn = makeNode(item);
    ++pbst->len;

    if (pbst->root == NULL)
        pbst->root = newn;
    else
        addNode(newn, pbst->root, call);

    return true;
}

bool BstreeInTree(const Item * pi, const Tree * pbst, Comp call)
{
    return (seekItem(pi, pbst, call).child == NULL)? false: true;
}

bool BstreeDelItem(Item * pi, Tree * pt, Comp call)
{
    Pair pa;

    if (pt->len == 0)
        return false;

    pa = seekItem(pi, pt, call);

    if (pa.child == NULL)
        return false;

    else if (pa.parent == NULL)
        delNode(&pt->root);

    else if (pa.parent->left == pa.child)
        delNode(&pa.parent->left);

    else
        delNode(&pa.parent->right);

    --pt->len;

    return true;
}

void EmptyTheBstree(Tree * pbst)
{
    dfClear(pbst->root);
}

static void dfClear(void * bstn)
{
    Node * node;

    if (bstn == NULL)
        return;
    else {
       node = (Node *)bstn;

       dfClear(node->left);
       dfClear(node->right);

       free(bstn);
    }
}

static Pair seekItem(const Item * pi, const Tree * pt, Comp comp)
{
    Pair look;
    look.parent = NULL;
    look.child = pt->root;
    int res;

    while (look.child != NULL) {
        ;
        if ((res = (*comp)(pi, &look.child->item))== 0)
            break;

        else if(res > 1) {
            look.parent = look.child;
            look.child = look.child->right;

        } else {
            look.parent = look.child;
            look.child = look.child->left;
        }

    }

    return look;
}

static void delNode(Node ** pn)
{
    Node * tmp;
    if ((*pn)->right == NULL) {
        tmp = *pn;
        *pn = (*pn)->left;
        free(tmp);

    } else if((*pn)->left == NULL) {
        tmp = *pn;
        *pn = (*pn)->right;
        free(tmp);

    } else {
        for (tmp=(*pn)->left; tmp->right != NULL; tmp = tmp->right)
            ;
            tmp->right = (*pn)->right;

            tmp = (*pn);
            *pn = (*pn)->left;
            free(tmp);
    }
}

void Traverse(const Tree * pt, BstCall call)
{
    if (pt->root != NULL)
        inOrder(pt->root, call);
}

static void inOrder(const Node * pn, BstCall call)
{
    if (pn == NULL)
        return;

    inOrder(pn->left, call);
    (*call)(&pn->item, pn->count);
    inOrder(pn->right, call);

}

//使用dfs实现的搜索
//static bool dfs(const Item * pi, const Node * pn)
//{
//    int res = (*comp)(pi, &pn->item);
//
//    if (pn == NULL)
//        return false;
//
//    else if (0 == res) {
//        return true;
//
//    } else if (0 < res) {
//        dfs(pi, pn->right);
//
//    } else {
//        dfs(pi, pn->left);
//    }
//}

//static void dfRmItem(const Item *pi, Node * pn, Node * parent)
//{
//    extern Comp comp;
//
//    int res = (*comp)(pi, &pn->item);
//
//    if (pn == NULL)
//        return;
//
//    if (res == 0) {
//        dfs_flag = true;
//        rmItemLink(pn, parent);
//        return;
//
//    } else
//
//        dfRmItem(pi, res>0 ? pn->right: pn->left, pn);
//}
//
//用方法delNode 体现了指针的强大能力:
//static void rmItemLink(Node * pn, Node * parent)
//{
//    Node * l = pn->left;
//    Node * r = pn->right;
//    Node * replace;
//
//    //用 binary 来记录子节点状态.
//    //lowest bit 为 l节点, first bit为r
//    char chi = 0;
//
//    free(pn);
//
//    if (l != NULL)
//        chi |= 1;
//
//    if (r != NULL)
//        chi |= 2;
//
//    //这里如果parent 为NULL 表示树已经清空了
//    if (chi == 0)
//        return;
//
//    replace = ((chi & 1) == 1)? l: r;
//
//    //第一步 将待rm节点的一个子节点接到parent上(默认为l)
//    if (parent != NULL)
//        parent->left ==pn?
//            (parent->left = replace):
//            (parent->right = replace);
//    else
//        newRoot = replace;
//
//    //剩下的节点一定是右节点
//    if (chi > 2) {
//        while (l->right)
//            l = l->right;
//
//        l->right = r;
//    }
//}

//等于的情况默认算在右侧
static void addNode(Node * node, Node * pn, Comp call)
{
    if (call(&node->item, &pn->item) < 0)
    {
        if (pn->left == NULL)
            pn->left = node;
        else
            addNode(node, pn->left, call);

    } else {
        if (pn->right == NULL)
            pn->right = node;
        else
            addNode(node, pn->right, call);
    }
}

static Node * makeNode(const Item * item)
{
    Node * newn;

    newn = (Node *)malloc(sizeof(Node));
    if (NULL == newn) {
        fprintf(stderr, "allocate memory failed!");
        exit(EXIT_FAILURE);
    }

    copyItemToNode(*item, newn);
    newn->left = newn->right = NULL;
    newn->count = 1;

    return newn;
}

static void copyItemToNode(Item item, Node * pn)
{
    pn->item = item;
}
